//SamXIAO
#include <bits/stdc++.h>
using namespace std;
#define szCNT_OF(x) (sizeof(x) / sizeof(x[0]))
#define MAX_LEN  1 * 1000 * 1000 + 86
#define MODN 32767

int f[MAX_LEN] = {0, 1, 2};

void genfib() {
   for (int i = 2; i < MAX_LEN; i++)
      f[i] = (2*f[i - 1] + f[i - 2]) % MODN;
}

void work1() {
   int n;
   scanf("%d", &n);
   genfib();
   for (int i = 0; i < n; i++) {
      int x;
      scanf("%d", &x);
      printf("%d\n", f[x]);
   }
}

int main() {
   work1();
   return 0;
}
